package com.leetcodehot.problems;

public class problems34 {
    /**
     * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
     * <p>
     * 如果数组中不存在目标值 target，返回 [-1, -1]。
     */

    /**
     * 二分查找的要点在于循环不变量：
     * 我是在看了这篇文章，https://blog.csdn.net/groovy2007/article/details/78309120，里那句“关键不在于区间里的元素具有什么性质，而是区间外面的元素具有什么性质。”之后醍醐灌顶，建立了我自己的二分查找心智模型，和up主的有些类似。
     *
     * 也就是看最终左右指针会停在哪里。
     * 如果我们要找第一个大于等于x的位置，那么我就假设L最终会停在第一个大于等于x的位置，R停在L的左边。
     * 这样按照上面那句话，可以把循环不变式描述为“L的左边恒小于x，R的右边恒大于等于x”，这样一来，其他的各种条件就不言自明了。
     * 比如循环条件肯定是L小于R，因为我假设R停在L的左边。
     * 而L和R转移的时候，根据循环不变式，如果mid小于x，肯定要令L等于mid+1，如果大于等于x，就令R等于mid-1。
     * 至于初始的时候L和R怎么选，也是看循环不变式，只需要保证初始L和R的选择满足“L的左边恒小于x，R的右边恒大于等于x”，并且不会出现越界的情况即可，L必为0，因为0左边可以看作负无穷，恒小于x，R取第一个一定满足条件的（防止mid取到非法值），例如n-1（n开始可以看作正无穷，恒大于等于x，如果保证x在数组里可以选择n-2，其实大于等于n也满足不变式，但是mid可能会取非法值），而且这样一来即使是搜索数组的某一段，也可以很方便根据这个条件地找到初始位置。
     *
     * 如果假设L最终会停在第一个大于等于x的位置，R停在L的位置，那么循环不变式就是“L的左边恒小于x，R以及R的右边恒大于等于x”，这样的话，循环条件就是L等于R的时候退出；转移的时候R=mid；初始时，一般取R=n（如果保证x在数组里，也可以取n-1）。
     *
     * 其他的情况也类似，比较直观的推导方法就是在要找的位置的分界处（比如在第一个大于等于x的位置后面）画一条线，然后假定L和R最终会停在这条线的左边还是右边，接着倒推各种条件即可。
     */
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        //找到第一个target的位置 和 最后一个target的位置
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) {
                //合法部分
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        //判断r+1,也等于l也就是 上一轮的m是否合法，如果合法即找到了
        if (l == n || nums[l] != target) {
            return new int[]{-1, -1};
        }
        int[] res = new int[2];
        res[0] = l;
        l = 0;
        r = n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target + 1) {
                //合法部分
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        res[1] = l - 1;
        return res;
    }
}
